package main

import "fmt"

// Definition for singly-linked list.
type ListNode struct {
	Val  int
	Next *ListNode
}

func (ll *ListNode) Print() {
	if ll == nil {
		return
	}
	cur := ll
	for cur != nil {
		fmt.Printf("%d\t", cur.Val)
		cur = cur.Next
	}
	fmt.Println()
}
func partition(head *ListNode, x int) *ListNode {
	//1. 定义虚拟头结点与指针变量
	smallHead := &ListNode{Val: -1} //较小值链表的虚拟头节点
	smallCur := smallHead           //较小值链表的操作指针变量

	largeHead := &ListNode{Val: -1} //较大值链表的虚拟头节点
	largeCur := largeHead           //较大值链表的操作指针变量

	cur := head //原链表的操作指针变量

	//2. 循环比较链表的节点值
	for cur != nil {
		if cur.Val < x {
			smallCur.Next = cur //将当前节点衔接到较小值链表中
			smallCur = cur      //移动操作节点指针变量

		} else {
			largeCur.Next = cur //将当前节点衔接到较大值链表中
			largeCur = cur      //移动操作节点指针变量

		}
		cur = cur.Next //移动当前操作节点的指针变量
	}

	//3. 处理较小值、较大值链表
	largeCur.Next = nil            //较大值组成的链表，末尾指向Null
	smallCur.Next = largeHead.Next //衔接2个链表
	return smallHead.Next          //返回链表：头节点为值较小的链表
}
func main() {
	head := &ListNode{Val: 1}
	head.Next = &ListNode{Val: 4}
	head.Next.Next = &ListNode{Val: 3}
	head.Next.Next.Next = &ListNode{Val: 2}
	head.Next.Next.Next.Next = &ListNode{Val: 5}
	head.Next.Next.Next.Next.Next = &ListNode{Val: 2}
	head.Print()

	node := partition(head, 3)
	node.Print()
}
